package LeetCode.Leet400_499.Leet430_439.Leet435;

import java.util.Arrays;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/5/29 10:36
 * @Description TODO: 方法一    模拟（贪心）  52ms    70.67%
 */
class Solution_1 {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 排序，按照区间期间升序排序
        Arrays.sort(intervals, (o1, o2) -> {
            return o1[0] - o2[0];
        });
        int count = 0;  // 重叠的区间个数
        int minEndIndex = intervals[0][1];  // 当前最小的右边界
        for (int i = 1; i < intervals.length; i++) {
            // 如果出现一个子区间的左边界小于当前最小的右边界，说明多了一个重叠的子区间
            if (intervals[i][0] < minEndIndex) {
                count++;
                // 出现重叠区间，则更新当前最小的右边界
                minEndIndex = Math.min(minEndIndex, intervals[i][1]);
            } else {
                // 找到一个非重叠子区间，更新右边界为当前区间右边界，开始下一轮寻找
                minEndIndex = intervals[i][1];
            }

        }
        // 需要移除区间的最小数量，即为重叠区间个数
        return count;
    }
}
